﻿using System;
using System.Collections.Generic;
using System.Text;

namespace FeCMS.CommonFunction
{
    /// <summary>
    ///     算法类，一些常用的算法
    /// </summary>
    public class Algorithm
    {
        /// <summary>
        ///     插值查找算法
        /// </summary>
        /// <param name="array">要查找的数组</param>
        /// <param name="n">数组长度</param>
        /// <param name="key">要查找的值</param>
        /// <returns></returns>
        public static bool SqDichotomySearch(int[] array, int n, int key)
        {

            //分别为数组的上标，下标，查找码的估算位置
            int low = 0,
                high = n - 1,
                pos;
            if ( n==0 || array[low] > key || array[high] < key)
                return false;
            while (low <= high)
            {
                if (low == high)
                {
                    if (key == array[low])
                        return true;
                    else
                        return false;
                }
                pos = (key - array[low]) / (array[high] - array[low]) * (high - low) + low;
                if (key == array[pos])
                {
                    //查到结果
                    return true;
                }
                if (key > array[pos])
                    low = pos + 1;
                else
                    high = pos - 1;
            }
            //没有找到
            return false;
        }

        /// <summary>
        ///     快速插值算法
        /// </summary>
        /// <param name="array">要插入的数组</param>
        /// <param name="key">要插入的值</param>
        /// <returns></returns>
        public static int[] SqDichotomyInsert(int[] array, int key)
        {
            //特殊情况，数组为长度0
            if(array.Length==0)
            {
                return new int[]{key};
            }

            int[] newArray = new int[array.Length + 1];
            //数在数组之前
            if (key < array[0])
            {
                newArray[0] =key;
                Array.Copy(array, 0, newArray, 1, array.Length);
                return newArray;
            }
            //数在数组之后
            if (key > array[array.Length - 1])
            {
                newArray[array.Length] = key;
                Array.Copy(array, 0, newArray, 0, array.Length);
                return newArray;
            }
            //数在中间
            bool isInsert =false;
            for (int i = 0, j = array.Length; i < j; i++)
            {
                if (!isInsert)
                {
                    //遇到值相等,不插入,直接返回原数组
                    if (array[i] == key)
                    {
                        return array;
                    }
                    //小于当前值
                    if (array[i] < key)
                    {
                        newArray[i] = array[i];
                        continue;
                    }
                    //大于当前值
                    if (array[i] > key)
                    {
                        newArray[i] = key;
                        newArray[i + 1] = array[i];
                        isInsert = true;
                    }
                }
                else
                {
                    newArray[i + 1] = array[i];
                }
            }
            return newArray;
        }

        /// <summary>
        ///     快速排序法
        /// </summary>
        /// <param name="array">排序的数组</param>
        /// <param name="left">数组中的第一个元素的位置</param>
        /// <param name="right">数组中最后一个元素的位置</param>
        /// <returns></returns>
        public static void QuickSort(int[] array, int left, int right)
        {
            int i, j, pivot, temp;
            if (left >= right)
                return;
            i = left;
            j = right + 1;
            pivot = array[left];
            while (true)
            {
                do
                {
                    i++;
                } while (array[i] < pivot && i < right); //从左向右寻找大于支点元素
                do
                {
                    j--;
                } while (array[j] > pivot && j > 0);     //从右向左寻找小于支点元素
                if (i >= j)
                    break;
                else     //满足i<j则交换i和j位置元素值
                {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
            array[left] = array[j];
            array[j] = pivot;     //以a[j]为新支点，j位置左边元素值均小于a[j],j位置右边元素值均大于a[j]
            QuickSort(array, left, j - 1);      //递归排序
            QuickSort(array, j + 1, right);
        }

        /// <summary>
        ///     多个数组合并，并去除重重数组
        /// </summary>
        /// <param name="args">数组参数</param>
        /// <returns></returns>
        public static int[] ArrayMergeToRepeat(params int[][] args)
        {
            int len=0,temp=-1;
            int[] array =new int[0];
            //合并多个数组
            for (int i = 0, j = args.Length; i < j; i++)
            {
                len += args[i].Length;
                int[] newBuffer =new int[len];
                Array.Copy(array, newBuffer, array.Length);
                Array.Copy(args[i], 0, newBuffer, array.Length, args[i].Length);
                //Array.Copy(args[i], array, array.Length);
                array = newBuffer;
            }
            //快速排序
            QuickSort(array, 0, array.Length-1);
            //弄个空数组存去重
            len =0;
            int[] arrayBuffer = new int[array.Length];
            for (int i = 0, j = array.Length; i < j; i++)
            {
                if(array[i]!=temp)
                {
                    temp =array[i];
                    arrayBuffer[len++] = temp;
                }
            }
            array = new int[len];
            Array.Copy(arrayBuffer, 0, array,0, len);
            return array;
        }
    }
}
